const int N = 1010;
class Solution {
public:
    
    bool dp[N][N];
    
    string longestPalindrome(string s) {
        int n = s.size();
        s = ' ' + s;
        
        int m = 0;
        string res;
        
        for (int i = 1; i <= n; i ++ ) {
            dp[i][i] = true;
            for (int j = 1; j <= i; j ++ ) {
                if (s[i] != s[j]) dp[i][j] = false;
                else {
                    if (i == j + 1) dp[i][j] = true;
                    else dp[i][j] = (dp[i - 1][j + 1] || dp[i][j]);
                    
                    if (dp[i][j] && i - j + 1 > m) m = i - j + 1, res = s.substr(j, m);
                }
            }
        }
        
        return res;
        
    }
};
